package com.scheuk.puzzles;

public class Algorithms {
	
	//fibonocci
	static long fib(int n) {
		if (n == 1 || n == 2) return 1;
		return fib(n-1) + fib(n-2);
	}
	
	//fibonocci with memorization
	static long fibMem(int n) {
	    //if n is 1 or 2, return 1;
	    if (n == 1 || n == 2) return 1;
	    //if memo[n] is not zero, return memo[n];
	    long[] memo = null;
		memo[n] = fibMem(n-1) + fibMem(n-2);
	    return memo[n];
	 }
	
    
	// recursive implementation Euclid's algorithm
    public static int gcd(int p, int q) {
        if (q == 0) return p;
        else return gcd(q, p % q);
    }

    // non-recursive implementation Euclid's algorithm
    public static int gcd2(int p, int q) {
        while (q != 0) {
            int temp = q;
            q = p % q;
            p = temp;
        }
        return p;
    }
    
    /*
     * @TODO test out
     */
    public static int[] sieveDyn()
    {
    	int limit = 10000000, n = 1, sqrt = (int) Math.sqrt(limit);
    	int m = limit/2;
    	boolean[] nums = new boolean[m + 1];
    	int[] primes = new int[664579];
    	int i, k;

    	while (n <= sqrt) {
    	  int x = (n<<1)+1;
    	  for (i = n+x; i <= m; nums[i] = true, i+=x);
    	  for (n++; nums[n]; n++);
    	}

    	primes[0] = 2;
    	for (i = 1, k = 1; i < nums.length; i++) {
    	  if (!nums[i])
    	    primes[k++] = (i<<1)+1;
    	}
    	return primes;
    }
	
	public static void main(String[] args) {
		/**
		int p = Integer.parseInt("12");
        int q = Integer.parseInt("24");
        int d  = gcd(p, q);
        int d2 = gcd2(p, q);
        System.out.println("gcd(" + p + ", " + q + ") = " + d);
        System.out.println("gcd(" + p + ", " + q + ") = " + d2);
        **/
		
		long startFib = System.currentTimeMillis();
		System.out.println("Fib(5) = " + fib(4000000));
		long endFib = System.currentTimeMillis();
		System.out.println((endFib - startFib) + " ms");
		
		/*long startFibMem = System.currentTimeMillis();
		System.out.println("FibMem(5) = " + fibMem(5));
		long endFibMem = System.currentTimeMillis();
		System.out.println((endFibMem - startFibMem) + " ms");*/
	}

}
